#pragma once

namespace zzz{
template <typename T1, typename T2>
struct HaarCoeff1D;
template <typename T1, typename T2>
struct HaarCoeff1DScale;

template <typename T1, typename T2>
struct HaarCoeff1D
{
  typedef T1 Index_Type;
  typedef T2 Value_Type;
  struct _coeff{
    Index_Type index;
    Value_Type value;
  }*Coeff;
  size_t Size;
  HaarCoeff1D()
  {
    Coeff=0;
    Size=0;
  }
  ~HaarCoeff1D()
  {
    delete[] Coeff;
  }
  void Clear()
  {
    delete[] Coeff;
    Coeff=0;
    Size=0;
  }
  HaarCoeff1D(const HaarCoeff1D<T1,T2> &c)
  {
    *this=c;
  }
  const HaarCoeff1D& operator=(const HaarCoeff1D<T1,T2> &c)
  {
    Clear();
    Size=c.Size;
    Coeff=new _coeff[c.Size];
    memcpy(Coeff,c.Coeff,sizeof(_coeff)*Size);
    return *this;
  }
  void LoadFromData(Value_Type *data, Index_Type size, Value_Type threshold=0)
  {
    Clear();
    int len=0;
    for (Index_Type i=0; i<size; i++)
      if (abs(data[i])>threshold) len++;
    Size=len;
    Coeff=new _coeff[len];
    Index_Type cur=0;
    for (Index_Type i=0; i<size; i++)
      if (abs(data[i])>threshold)
      {
        Coeff[i].index=cur;
        Coeff[i].value=data[i];
        cur++;
      }
  }
  void SaveToData(Value_Type *data, Index_Type size)
  {
    memset(data,0,sizeof(Value_Type)*size);
    for (int i=0; i<Size; i++)
      data[Coeff[i].index]=Coeff[i].value;
  }
  inline Value_Type Dot(const HaarCoeff1D<T1,T2> &c)
  {
    Value_Type ret=0;
    int cur1=0,cur2=0;
    for (cur1=0;cur1<Size;cur1++)
    {
      while(cur2<c.Size && Coeff[cur1].index>c.Coeff[cur2].index) cur2++;
      if (Coeff[cur1].index==c.Coeff[cur2].index) ret+=Coeff[cur1].value*c.Coeff[cur2].value;
    }
    return ret;
  }
  inline Value_Type Dot(const HaarCoeff1DScale<T1,T2> &c)
  {
    Value_Type ret=0;
    int cur1=0,cur2=0;
    for (cur1=0;cur1<Size;cur1++)
    {
      while(cur2<c.Size && Coeff[cur1].index>c.Coeff[cur2].index) cur2++;
      if (Coeff[cur1].index==c.Coeff[cur2].index) ret+=Coeff[cur1].value*c.Coeff[cur2].value;
    }
    return ret*c.Scale;
  }
};

template <typename T1, typename T2>
struct HaarCoeff1DScale
{
  typedef T1 Index_Type;
  typedef T2 Value_Type;
  struct _coeff{
    Index_Type index;
    Value_Type value;
  }*Coeff;
  size_t Size;
  float Scale;
  HaarCoeff1D()
  {
    Coeff=0;
    Size=0;
    Scale=1.0f;
  }
  ~HaarCoeff1D()
  {
    delete[] Coeff;
  }
  void Clear()
  {
    delete[] Coeff;
    Coeff=0;
    Size=0;
    Scale=1.0f;
  }
  HaarCoeff1D(const HaarCoeff1DScale<T1,T2> &c)
  {
    *this=c;
  }
  const HaarCoeff1D& operator=(const HaarCoeff1DScale<T1,T2> &c)
  {
    Clear();
    Size=c.Size;
    Scale=c.Scale;
    Coeff=new _coeff[c.Size];
    memcpy(Coeff,c.Coeff,sizeof(_coeff)*Size);
    return *this;
  }
  template <typename T>
  void LoadFromData(T *data, Index_Type size, T threshold=0)
  {
    Clear();
    int len=0;
    T minvalue=numeric_limits<T>::max(),maxvalue=numeric_limits<T>::min();
    for (Index_Type i=0; i<size; i++)
    {
      if (abs(data[i])>threshold) 
      {
        len++;
        if (minvalue>data[i]) minvalue=data[i];
        if (maxvalue<data[i]) maxvalue=data[i];
      }
    }
    maxvalue=(abs(minvalue)<abs(maxvalue))?abs(maxvalue):abs(minvalue);
    Scale=(float)maxvalue/(float)numeric_limits<Value_Type>::max();
    Size=len;
    Coeff=new _coeff[len];
    Index_Type cur=0;
    for (Index_Type i=0; i<size; i++)
      if (abs(data[i])>threshold)
      {
        Coeff[i].index=cur;
        Coeff[i].value=(Value_Type)(data[i]/Scale);
        cur++;
      }
  }
  void SaveToData(Value_Type *data, Index_Type size)
  {
    memset(data,0,sizeof(Value_Type)*size);
    for (int i=0; i<Size; i++)
      data[Coeff[i].index]=Coeff[i].value*Scale;
  }
  inline Value_Type Dot(const HaarCoeff1D<T1,T2> &c)
  {
    float ret=0;
    int cur1=0,cur2=0;
    for (cur1=0;cur1<Size;cur1++)
    {
      while(cur2<c.Size && Coeff[cur1].index>c.Coeff[cur2].index) cur2++;
      if (Coeff[cur1].index==c.Coeff[cur2].index) ret+=Coeff[cur1].value*c.Coeff[cur2].value;
    }
    return ret*Scale;
  }

  inline Value_Type Dot(const HaarCoeff1DScale<T1,T2> &c)
  {
    float ret=0;
    int cur1=0,cur2=0;
    for (cur1=0;cur1<Size;cur1++)
    {
      while(cur2<c.Size && Coeff[cur1].index>c.Coeff[cur2].index) cur2++;
      if (Coeff[cur1].index==c.Coeff[cur2].index) ret+=Coeff[cur1].value*c.Coeff[cur2].value;
    }
    return ret*Scale*c.Scale;
  }

};
}